Field of the Invention
The present invention relates to an adaptive routing controller of a crossbar core module used in a crossbar routing switch.
In general, for a parallel processing system to have an excellent performance by concurrently processing tasks in parallel in a plurality of processors by using a plurality of processors, an interconnection network for connecting a plurality of processors plays a very important role. The interconnection network consists of a routing switch, a backplane and a cable. The routing switch is a nucleolus part which performs a function of interconnection network.
Since the function of the routing switch is determined according to a structure and a function of each interconnection network, the routing switch of a particular interconnection network is designed and implemented to be adapted to the particular interconnection network. In addition, a routing controller must be designed to be adapted to a function and characteristics inherent to the routing switch. In other words, the routing controller which well supports the characteristics of the routing switch and provides an excellent performance and function plays a nucleolus role which determines the inherent characteristics, excellent function and performance of the routing switch. Furthermore, since this role leads to the characteristics and function of the interconnection network, the invention of the routing controller which well supports the inherent characteristics and provides the excellent performance and function is very important.
A switching device invented by G. P. Balboni et al. is a switching element for performing a self routing control in a multistage packet switching interconnection network(refer to G. P. Balboni et al., . . . Switching Element for Self-routing Multistage Packet-switching Interconnection Networks", U.S. Pat. No. 4,890,281, December 1989). The switching device is a unit device having 2X2 switch configuration and is a simple switching device controlled by one bit among a tag portion of a packet. The switching device does not have an arbitration concept. It performs the routing control by the simple tag bit, and has a two port simultaneous transmission function for broadcasting transmission. The switching device does not provide an arbitration and adaptive routing control method.
An interconnection network device proposed by S. B. Kim et al. is a switching device for performing the routing control in an interconnection network of mesh type(refer to S. B. Kim et al. interconnection network device", KR 66825, October 1993). The switching device can obtain a plurality of routings while avoiding a deadlock state in the interconnection network of mesh type, and has a routing control unit which performs the routing control only to the address determined by the packet tag and perform the arbitration via a simple 3X1 selector. The switching device is implemented with its own packet type and routing control method and provides only a basic routing control method.
A multipath torus switching apparatus invented by Olnowich and Williams is a switching device of Wormhole routing having small delay time in the interconnection network of torus mesh type(refer to H. T. Olnowich and A. R. Williams, . . . Multipath torus switching apparatus", EP 0588104A2, December 1994). The switching device is invented to determine a routing control port by adding a multipath establishment function to an existing torus switch. The switching device consists of four single routing controller and a multipath controller and selects an output port by using a connection command of packet. However, the switching device does not suggest a scheme of arbitration method, and has different packet type and routing control method. Although the switching device has a multipath control function similar to the adaptive routing control, since the configuration and method thereof are different, it can not be properly used to a crossbar routing switch.
An adaptive routing control method invented by Nugent is a method in which an additional connection path is established by connecting to an interconnection network of mesh type an additional interconnection network of identical type and thereafter performs the routing control via the additional connection path in case that a problem occurs to an existing routing or a transmission is impossible. (refer to Nugent, . . . Adaptive Message Routing for Multi-Dimensional Networks," U.S. Pat. No. 5,175,733, December 1992). The adaptive routing control method is a method in which when the routing control is impossible to X-direction and Y-direction, the adaptive routing control is performed to Z-direction by establishing an additional connection path to Z-direction. In case of the routing controller, it only performs a simple arbitration for two inputs and it is not appropriate to the adaptive routing control method and a switching device having a plurality of I/O ports.
An adaptive routing control switching device invented by A. H. Frey Jr. et al is a switching device for controlling the routing with a shortest distance up to a destination in a multi-dimension multi-node environment(refer to A. H. Frey Jr. et al., . . . Adaptive Routing in a Parallel Computing System". U.S. Pat. No. 5,181,017, January 1993). The switching device is a device by which only one packet which arrives fastest is effectively received by retrieving all routing possibly established from a source to a destination and transmitting simultaneously via all the paths. This method performs the adaptive routing control via a packet header, and the switching device provides only a mechanism for transmission and cancellation of the packet. The transmission of packet is terminated by only one time of packet transmission in other interconnection network, while there is a problem in the interconnection network of the switching device described above that a separate packet transmission is necessary for confirmation.
Most of conventional inventions are switching devices or appropriate arbitration methods for the multi-stage interconnection network or the mesh type interconnection network, and in addition, the adaptive routing control methods have many different methods and constitutions, therefore, most of conventional inventions can not provide routing controller adapted to the crossbar routing switch.